/**
 * 79. 单词搜索
 * https://leetcode-cn.com/problems/word-search/
 */

/**
 * @param {string[]} chars
 * @param {number} index
 * @param {string[][]} board
 * @param {number} i
 * @param {number} j
 * @param {number[][]} signs
 * @param {number} sign
 */
function search(chars, index, board, i, j, signs, sign) {
  if (index >= chars.length) return true;
  const { length: n } = board;
  const { length: m } = board[0];
  if (i < 0 || j < 0 || i >= n || j >= m) return false;
  if (signs[i][j] === sign) return false;
  const char = chars[index];
  const start = board[i][j];
  if (char !== start) return false;
  signs[i][j] = sign;
  if (
    search(chars, index + 1, board, i + 1, j, signs, sign)
    || search(chars, index + 1, board, i, j + 1, signs, sign)
    || search(chars, index + 1, board, i - 1, j, signs, sign)
    || search(chars, index + 1, board, i, j - 1, signs, sign)
  ) return true;
  signs[i][j] = sign - 1;
  return false;
}

/**
 * @param {string[][]} board
 * @param {string} word
 * @return {boolean}
 */
function exist(board, word) {
  const { length: n } = board;
  const { length: m } = board[0];
  const { length: count } = word;
  if (count > m * n) return false;
  const chars = word.split('');
  const signs = new Array(n);
  for (let i = 0; i < n; i += 1) {
    signs[i] = new Array(m).fill(-1);
  }
  for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < m; j += 1) {
      if (search(chars, 0, board, i, j, signs, i * n + j)) return true;
    }
  }
  return false;
}

console.log(exist([['A', 'B', 'C', 'E'], ['S', 'F', 'E', 'S'], ['A', 'D', 'E', 'E']], 'ABCESEEEFS') === true);
console.log(exist([['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], 'ABCCED') === true);
console.log(exist([['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], 'SEE') === true);
console.log(exist([['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], 'ABCB') === false);
